package com.alt.www.find;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.io.File;
import java.util.Scanner;

/**
 * Created by 27340 on 2017/8/1.  sss
 */
public class UF {
    private int[] id;
    private int count;
    private int[] sz;

    public UF(int N,boolean isWeight){
        if(isWeight){
            count = N;
            id = new int[N];
            for(int i=0;i<N;i++){
                id[i] = i;
            }
            sz = new int[N];
            for(int i=0;i<N;i++){
                sz[i] = 1;
            }
        }else{
            count = N;
            id = new int[N];
            for(int i=0;i<N;i++){
                id[i] = i;
            }
        }

    }


    public void union(int p, int q){
        int pID = id[p];
        int qID = id[q];
        if(pID == qID){
            return;
        }
        for(int i=0;i<id.length;i++){
            if(pID == id[i]){
                id[i] = qID;
            }
        }
        count --;
    }

    public void quickUnion(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        id[p] = qRoot;
        count--;
    }

    public int quickFind(int index){
        while (index!=id[index])
            index=id[index];
        return index;
    }

    public void unionWeight(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        if(sz[pRoot]<sz[qRoot]){
            id[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else{
            id[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
        count--;
    }



    public int find(int p){
        return id[p];
    }


    public boolean connected(int p, int q){
        return find(p)==find(q);
    }

    public static void main(String[] args){
//        int N = StdIn.readInt();
//        UF uf = new UF(N);
//        while (!StdIn.isEmpty()){
//            int p = StdIn.readInt();
//            int q = StdIn.readInt();
//            if(uf.connected(p, q)){
//                continue;
//            }
//            uf.union(p,q);
//            StdOut.println(uf.count + "components");
//        }

        File f= new File("F:" + File.separator +"tinyUF.txt");
        Scanner scan = null;
        try{
            scan = new Scanner(f);//从文件接收数据  
        } catch (Exception e){
        }
        int N = scan.nextInt();
        UF uf = new UF(N,true);
        while (scan.hasNext()){
            int p = scan.nextInt();
            int q = scan.nextInt();
            if(uf.connected(p, q)){
                continue;
            }
            uf.union(p,q);
            System.out.println(uf.count + "components");
        }
    }
}
